#ifndef BT_H_
#define BT_H_

#include <cstddef>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <type_traits>


namespace lxj
{

template<class T, std::enable_if_t<std::is_arithmetic_v<T>, int> = 0>
struct Node {
    T     _value;
    Node* left;
    Node* right;
};

template<class T, std::enable_if_t<std::is_arithmetic_v<T>, int> = 0>
class BinaryTree {
    Node<T>* _head;
    size_t   _size;

public:
    BinaryTree(Node<T>* head) : _head(head) {}

    template<typename Iter>
    BinaryTree(Iter first, Iter last)
    {
        std::_Adl_verify_range(first, last);

        auto       ufirst = std::_Get_unwrapped(first);
        const auto ulast  = std::_Get_unwrapped(last);
        using type        = std::remove_cv_t<std::remove_pointer_t<decltype(ufirst)>>;
        static_assert(std::is_same_v<T, type>, "模板类型参数不匹配");

        _head = new Node<T>{._value = *(ufirst), .left = nullptr, .right = nullptr};
        ufirst++;
        _size                    = ulast - ufirst;
        decltype(_head)      cur = nullptr;
        std::queue<Node<T>*> node_que;
        node_que.push(_head);
        while (!node_que.empty()) {
            cur = node_que.front();
            node_que.pop();
            if (ulast - ufirst > 0) {
                cur->left = new Node<T>{._value = *(ufirst++), .left = nullptr, .right = nullptr};
                node_que.push(cur->left);
            }
            if (ulast - ufirst > 0) {
                cur->right = new Node<T>{._value = *(ufirst++), .left = nullptr, .right = nullptr};
                node_que.push(cur->right);
            }
        }
        while (!node_que.empty()) {
            node_que.pop();
        }
    }

    BinaryTree(const BinaryTree&) = delete;

    BinaryTree(BinaryTree&& other) : _head(other._head), _size(other._size)
    {
        other._head = nullptr;
    }

    ~BinaryTree()
    {
        std::queue<Node<T>*> node;
        node.push(_head);
        Node<T>* cur = nullptr;
        while (!node.empty()) {
            cur = node.front();
            node.pop();
            cur->left == nullptr ? (void)0 : node.push(cur->left);
            cur->right == nullptr ? (void)0 : node.push(cur->right);
            delete cur;
        }
    }

    size_t size() const { return _size; }

    // 先序遍历（递归版）中左右
    void p_print(const Node<T>* node) const
    {
        if (node == nullptr) return;
        auto value = node->_value;
        std::cout << value << ", ";
        p_print(node->left);
        p_print(node->right);
    }
    void preorder_print() const
    {
        p_print(_head);
        std::puts("");
    }

    // 用栈实现先序遍历
    void pd_print() const
    {
        if (_head == nullptr) return;

        std::stack<Node<T>*> node_sta;
        node_sta.push(_head);
        Node<T>* cur = nullptr;
        while (!node_sta.empty()) {
            cur = node_sta.top();
            node_sta.pop();
            auto value = cur->_value;
            std::cout << value << ", ";
            cur->right == nullptr ? (void)0 : node_sta.push(cur->right);
            cur->left == nullptr ? (void)0 : node_sta.push(cur->left);
        }
        std::puts("");
    }

    // 中序遍历（递归版）左中右
    void i_print(const Node<T>* node) const
    {
        if (node == nullptr) return;
        i_print(node->left);
        auto value = node->_value;
        std::cout << value << ", ";
        i_print(node->right);
    }
    void inorder_print() const
    {
        i_print(_head);
        std::puts("");
    }

    // 用栈实现中序遍历
    void io_print() const
    {
        if (_head == nullptr) return;

        std::stack<Node<T>*> node_sta;
        Node<T>*             cur = _head;
        while (!node_sta.empty() || cur != nullptr) {
            if (cur != nullptr) {
                node_sta.push(cur);
                cur = cur->left;
            }
            else {
                cur = node_sta.top();
                node_sta.pop();
                auto value = cur->_value;
                std::cout << value << ", ";
                cur = cur->right;
            }
        }
        std::puts("");
    }

    // 后序遍历（递归版）左右中
    void po_print(const Node<T>* node) const
    {
        if (node == nullptr) return;
        po_print(node->left);
        po_print(node->right);
        auto value = node->_value;
        std::cout << value << ", ";
    }
    void postorder_print() const
    {
        po_print(_head);
        std::puts("");
    }

    // 用栈实现后序遍历(一个栈版本)
    void post_print1()
    {
        if (_head == nullptr) return;

        std::stack<Node<T>*> stack;
        stack.push(_head);
        Node<T>* h = _head;

        while (!stack.empty()) {
            Node<T>* cur = stack.top();
            if (cur->left != nullptr && h != cur->left && h != cur->right) {
                stack.push(cur->left);
            }
            else if (cur->right != nullptr && h != cur->right) {
                stack.push(cur->right);
            }
            else {
                auto value = stack.top()->_value;
                std::cout << value << ", ";
                h = stack.top();
                stack.pop();
            }
        }
        std::puts("");
    }
    // 用栈实现后序遍历(两个栈版本)
    void post_print2() const
    {
        if (_head == nullptr) return;

        std::stack<Node<T>*> input, output;
        Node<T>*             cur = nullptr;
        input.push(_head);
        while (!input.empty()) {
            cur = input.top();
            input.pop();
            output.push(cur);
            cur->left == nullptr ? (void)0 : input.push(cur->left);
            cur->right == nullptr ? (void)0 : input.push(cur->right);
        }
        while (!output.empty()) {
            auto value = output.top()->_value;
            std::cout << value << ", ";
            output.pop();
        }
        std::puts("");
    }

    // 层序遍历
    void level_print() const
    {
        if (_head == nullptr) return;

        std::queue<Node<T>*> node_que;
        node_que.push(_head);
        Node<T>* cur = nullptr;
        while (!node_que.empty()) {
            cur = node_que.front();
            node_que.pop();
            auto value = cur->_value;
            std::cout << value << ", ";
            cur->left == nullptr ? (void)0 : node_que.push(cur->left);
            cur->right == nullptr ? (void)0 : node_que.push(cur->right);
        }
        std::puts("");
    }
};

}   // namespace lxj

#endif